"""
    著名的八皇后问题
    1. 准备一个列表长度为8，其中下标素索引为行数，内容为列数
    2. 循环从第一列开始，逐个从第一行开始到第一行最后一行结束的所有情况（深度遍历（递归）+ 广度遍历（for））
    3. 深度遍历就是选找到的一种可行的结果，在尝试第二种
"""

maxSize = 8
count = 0
judgeNum = 0

arr = list([-1] * maxSize)


def try_method(n):
    """
        基本思想：(递归)
        1. 准备一个数组，用来防止每个皇后的位置，其中数组下标表示第几个皇后（行数），数组的值表示每个皇后的位置（列数）
        2. 从第0个皇后开始，循环判断每个位置知否能放置元素
        3. 如果可以放置元素，就递归尝试的下一个皇后可以放置的位置，知道找到最后一皇后的位置时打印结果（就是第一种摆法）
        4. 回溯到上一步，也就是摆放了7个元素的时候，且已经尝试了最后一行的上一种解法之后，去尝试下一种方法

        个人理解：
            for循环对应的每一列代表的广度遍历，for循环之中套入递归，表示的深度遍历，该思想是一个深度优先遍历经典使用；
    :param n: 第几个皇后
    """
    if n == maxSize:
        # 统计有多少中解法
        global count
        count += 1
        # 打印解法数组
        print(arr)
        return

    # 尝试八个位置（8列）
    for i in range(0, maxSize):
        # 循环行数
        arr[n] = i
        if judge(n):
            try_method(n + 1)


def judge(n):
    """
    方法描述：第n个皇后的位置是否可行
    注意：这里使用了全局变量 arr 所以应该有两个参数
    :param arr 到第n个皇后时已经摆放的位置所表示的数组
    :param n: 第n个皇后
    :return:
    """
    for i in range(0, n):
        global judgeNum
        judgeNum += 1
        if arr[i] == arr[n] or abs(n - i) == abs(arr[n] - arr[i]):
            return False
    return True


if __name__ == "__main__":
    try_method(0)
    print("共计有 {} 种方法".format(count))
    print("共计比较了%d次" % judgeNum)
